package com.dy.设计问题.InsertDeleteGetRandomO1;
/*
设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构。

insert(val)：当元素 val 不存在时，向集合中插入该项。
remove(val)：元素 val 存在时，从集合中移除该项。
getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。
示例 :

// 初始化一个空的集合。
RandomizedSet randomSet = new RandomizedSet();

// 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomSet.insert(1);

// 返回 false ，表示集合中不存在 2 。
randomSet.remove(2);

// 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomSet.insert(2);

// getRandom 应随机返回 1 或 2 。
randomSet.getRandom();

// 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomSet.remove(1);

// 2 已在集合中，所以返回 false 。
randomSet.insert(2);

// 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
randomSet.getRandom();
 */

import java.util.*;

/**
 * 添加和获取耗时O(1)是Array的特性，或者说是Map/Table的特性，思考下php的array就明白其实是index的mapping了。
 * Random要求O(1)那就是需要知道数据结构的大小，并且保证储存的元素是相邻的。
 *
 * 其实就是一个table/map，KEY是添加的元素，value是他储存在array中的位置；
 * 然后一个array和上面的table/map对应；
 * 再一个变量size记录总共有多少个元素，便于random.
 *
 * 将要删除的数字和数组的最后一个数字调换个位置，然后修改对应的哈希表中的值，这样我们只需要删除数组的最后一个元素即可，
 * 保证了常数时间内的删除。
 */
public class RandomizedSet {
    /** Initialize your data structure here. */
    Map<Integer,Integer> map;
    List<Integer> list;
    int size;
    public RandomizedSet() {
        map = new HashMap<>();
        list = new ArrayList<>();
        this.size = 0;
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if(map.containsKey(val)) return false;
        else{
            list.add(size,val);
            map.put(val,size++);
            return true;
        }

    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if(!map.containsKey(val)) {return false;}
        else{
            int tmp = list.get(size-1);//获得最后一个数
            map.put(tmp,map.get(val));//修改map里位置
            list.set(map.get(val),tmp);//修改list


            map.remove(val);
            size--;
            return true;

        }

    }

    /** Get a random element from the set. */
    public int getRandom() {
        Random rdm = new Random();
        return list.get(rdm.nextInt(size));
    }
}
